\chapter{The PID structure theorem}
\label{ch:PID_structure_theorem}
The main point of this chapter is to discuss a classification
theorem for finitely generated abelian groups.
This won't take long to do, and if you like, you can read
just the first section and then move on.

However, since I'm here, I will go ahead and state the result as a
special case of the much more general \emph{structure theorem}.
Its corollaries include
\begin{itemize}
	\ii All finite-dimensional vector spaces are $k^{\oplus n}$.
	\ii The classification theorem for finitely generated abelian groups,
	\ii The Jordan decomposition of a matrix from before,
	\ii Another canonical form for a matrix: ``Frobenius normal form''.
\end{itemize}

\section{Finitely generated abelian groups}
\label{sec:FTFGAG}
\begin{remark}
	We talk about abelian groups in what follows, but really the
	morally correct way to think about these structures is as $\ZZ$-modules.
\end{remark}
\begin{definition}
	An abelian group $G = (G,+)$ is \vocab{finitely generated}
	if it is finitely generated as a $\ZZ$-module.
	(That is, there exists a finite collection $b_1, \dots, b_m \in G$,
	such that every $x \in G$ can be written in the form
	$c_1 b_1 + \dots + c_m b_m$ for some $c_1, \dots, c_m \in \ZZ$.)
\end{definition}
\begin{example}
	[Examples of finitely generated abelian groups]
	\listhack
	\begin{enumerate}[(a)]
		\ii $\ZZ$ is finitely generated (by $1$).
		\ii $\Zc n$ is finitely generated (by $1$).
		\ii $\ZZ^{\oplus 2}$ is finitely generated (by two elements $(1,0)$ and $(0,1)$).
		\ii $\ZZ^{\oplus 3} \oplus \Zc9 \oplus \Zc{2016}$ is
		finitely generated by five elements.
		\ii $\Zc3\oplus\Zc5$ is finitely generated by two elements.
	\end{enumerate}
\end{example}
\begin{exercise}
	In fact $\Zc3\oplus\Zc5$ is generated by \emph{one} element.
	What is it?
\end{exercise}
You might notice that these examples are not very diverse.
That's because they are actually the only examples:
\begin{theorem}
	[Fundamental theorem of finitely generated abelian groups]
	\label{thm:fund_fg_abelian_group}
	Let $G$ be a finitely generated abelian group.
	Then there exists an integer $r$,
	prime powers $q_1$, \dots, $q_m$ (not necessarily distinct) such that
	\[
		G \cong \ZZ^{\oplus r} \oplus \Zc{q_1} \oplus \Zc{q_2} \oplus
		\dots \oplus \Zc{q_m}. \]
	This decomposition is unique up to permutation of the $\Zc{q_i}$.
\end{theorem}
\begin{definition}
	The \vocab{rank} of a finitely generated abelian group $G$ is the integer $r$ above.
\end{definition}

Now, we could prove this theorem, but it is more interesting to go for the gold
and state and prove the entire structure theorem.

\section{Some ring theory prerequisites}
\prototype{$R = \ZZ$.}
Before I can state the main theorem, I need to define a few terms for UFD's,
which behave much like $\ZZ$:
\begin{moral}
	Our intuition from the case $R = \ZZ$ basically carries over verbatim.
\end{moral}
We don't even need to deal with prime ideals and can factor elements instead.

\begin{definition}
	If $R$ is a UFD, then $p \in R$ is a \vocab{prime element}
	if $(p)$ is a prime ideal and $p \neq 0$.
	For UFD's this is equivalent to:
	if $p = xy$ then either $x$ or $y$ is a unit.
\end{definition}
So for example in $\ZZ$ the set of prime elements is $\{\pm2, \pm3, \pm5, \dots\}$.
Now, since $R$ is a UFD, every element $r$ factors into a product of prime elements
\[ r = u p_1^{e_1} p_2^{e_2} \dots p_m^{e_m} \]

\begin{definition}
	We say $r$ \vocab{divides} $s$ if $s = r'r$
	for some $r' \in R$. This is written $r \mid s$.
\end{definition}
\begin{example}
	[Divisibility in $\ZZ$]
	The number $0$ is divisible by every element of $\ZZ$.
	All other divisibility as expected.
\end{example}
\begin{ques}
	Show that $r \mid s$ if and only if the exponent of each prime in $r$ is
	less than or equal to the corresponding exponent in $s$.
\end{ques}

Now, the case of interest is the even stronger case when $R$ is a PID:
\begin{proposition}
	[PID's are Noetherian UFD's]
	If $R$ is a PID, then it is Noetherian and also a UFD.
\end{proposition}
\begin{proof}
	The fact that $R$ is Noetherian is obvious.
	For $R$ to be a UFD we essentially repeat the proof for $\ZZ$,
	using the fact that $(a,b)$ is principal in order to extract
	$\gcd(a,b)$.
\end{proof}

In this case, we have a Chinese remainder theorem for elements.
\begin{theorem}
	[Chinese remainder theorem for rings]
	Let $m$ and $n$ be relatively prime elements, meaning $(m) + (n) = (1)$.
	Then \[ R / (mn) \cong R/(m) \times R/(n). \]
\end{theorem}
Here the ring product is as defined in \Cref{ex:product_ring}.
\begin{proof}
	This is the same as the proof of the usual Chinese remainder theorem.
	First, since $(m,n)=(1)$ we have $am+bn=1$ for some $a$ and $b$.
	Then we have a map
	\[ R/(m) \times R/(n) \to R/(mn) \quad\text{by}\quad
		(r,s) \mapsto r \cdot bn + s \cdot am. \]
	One can check that this map is well-defined and an isomorphism of rings.
	(Diligent readers invited to do so.)
\end{proof}

Finally, we need to introduce the concept of a Noetherian $R$-module.
\begin{definition}
	An $R$-module $M$ is \vocab{Noetherian}
	if it satisfies one of the two equivalent conditions:
	\begin{itemize}
		\ii Its submodules obey the ascending chain condition:
		there is no infinite sequence of modules
		$M_1 \subsetneq M_2 \subsetneq \dots$.
		\ii All submodules of $M$ (including $M$ itself) are finitely generated.
	\end{itemize}
\end{definition}
This generalizes the notion of a Noetherian ring:
a Noetherian ring $R$ is one for which $R$ is Noetherian as an $R$-module.
\begin{ques}
	Check these two conditions are equivalent. (Copy the proof for rings.)
\end{ques}

\section{The structure theorem}
\label{sec:structure_thm}
Our structure theorem takes two forms:
\begin{theorem}
	[Structure theorem, invariant form]
	Let $R$ be a PID and let $M$ be any finitely generated $R$-module. Then
	\[ M \cong \bigoplus_{i=1}^m R/(s_i) \]
	for some $s_i$ (possibly zero)
	satisfying $s_1 \mid s_2 \mid \dots \mid s_m$.
	% These $s_i$ are unique up to multiplication by units.
\end{theorem}
\begin{corollary}
	[Structure theorem, primary form]
	\label{cor:structure_theorem_primary}
	Let $R$ be a PID and let $M$ be any finitely generated $R$-module. Then
	\[ M \cong R^{\oplus r}
		\oplus R/(q_1) \oplus R/(q_2) \oplus \dots \oplus R/(q_m) \]
	where $q_i = p_i^{e_i}$ for some prime element $p_i$ and integer $e_i \ge 1$.
	% The numbers $r$ and $q_i$ are unique up to permutation and multiplication by units.
\end{corollary}
\begin{proof}
	[Proof of corollary]
	Factor each $s_i$ into prime factors (since $R$ is a UFD),
	then use the Chinese remainder theorem.
\end{proof}
\begin{remark}
	In both theorems the decomposition is unique up to
	permutations of the summands.
\end{remark}

\section{Reduction to maps of free $R$-modules}
\begin{definition}
	A \vocab{free $R$-module} is a module of the form $R^{\oplus n}$
	(or more generally, $\bigoplus_I R$ for some indexing set $I$,
	just to allow an infinite basis).
\end{definition}
The proof of the structure theorem proceeds in two main steps.
First, we reduce the problem to a \emph{linear algebra} problem
involving free $R$-modules $R^{\oplus d}$.
Once that's done, we just have to play with matrices;
this is done in the next section.

Suppose $M$ is finitely generated by $d$ elements.
Then there is a surjective map of $R$-modules
\[ R^{\oplus d} \surjto M \]
whose image on the basis of $R^{\oplus d}$ are the generators of $M$.
Let $K$ denote the kernel.

We claim that $K$ is finitely generated as well.
To this end we prove that
\begin{lemma}[Direct sum of Noetherian modules is Noetherian]
	Let $M$ and $N$ be two Noetherian $R$-modules.
	Then the direct sum $M \oplus N$ is also a Noetherian $R$-module.
\end{lemma}
\begin{proof}
	It suffices to show that if $L \subseteq M \oplus N$,
	then $L$ is finitely generated.
	One guess is that $L = P \oplus Q$,
	where $P$ and $Q$ are the projections of $L$ onto $M$ and $N$.
	Unfortunately this is false
	(take $M = N = \ZZ$ and $L = \{(n,n) \mid n \in \ZZ\}$)
	so we will have to be more careful.

	Consider the submodules
	\begin{align*}
		A &= \left\{ x \in M \mid (x,0) \in L \right\} \subseteq M \\
		B &= \left\{ y \in N \mid \exists x \in M : (x,y) \in L \right\}
			\subseteq N.
	\end{align*}
	(Note the asymmetry for $A$ and $B$: the proof doesn't work otherwise.)
	Then $A$ is finitely generated by $a_1$, \dots, $a_k$,
	and $B$ is finitely generated by $b_1$, \dots, $b_\ell$.
	Let $x_i = (a_i, 0)$ and let $y_i = (\ast, b_i)$ be elements of $L$
	(where the $\ast$'s are arbitrary things we don't care about).
	Then $x_i$ and $y_i$ together generate $L$.
\end{proof}
\begin{ques}
	Deduce that for $R$ a PID, $R^{\oplus d}$ is Noetherian.
\end{ques}
Hence $K \subseteq R^{\oplus d}$ is finitely generated as claimed.
So we can find another surjective map $R^{\oplus f} \surjto K$.
Consequently, we have a composition
\begin{center}
\begin{tikzcd}
	& K \ar[rd, hook] \\
	R^{\oplus f} \ar[ru, surjective head] \ar[rr, "T"'] && R^{\oplus d} \ar[r, surjective head] & M
\end{tikzcd}
\end{center}
Observe that $M$ is the \emph{cokernel} of the linear map $T$,
i.e.\ we have that
\[ M \cong R^{\oplus d} / \img(T). \]
So it suffices to understand the map $T$ well.

\section{Uniqueness of primary form}

In this section, we will prove that if $M \cong R^{\oplus r} \oplus R/(q_1) \oplus R/(q_2) \oplus \cdots
\oplus R/(q_m)$, then the integer $r$ and the prime powers $q_i$ are unique, up to permutations.

First, we consider the case where $M$ is free.

\begin{theorem}
	[Uniqueness of free module's rank]
	For a commutative integral domain $R$,
	if a free module $M$ has a finite basis, then every other basis has the same number of elements.
\end{theorem}
It was mentioned once in \Cref{thm:dimension_theorem} that the strategy of the proof is to pass to the
field case. Indeed, we're going to pass to the field $F$ being the fraction field of $R$,
then directly apply the dimension theorem for vector spaces.
\begin{proof}
	As before, but we prove by contradiction this time.
	Assume $v_1, \dots, v_n$ is a basis for the free module $M$ of rank $n$,
	while $w_1, \dots, w_m$ are any elements of $M$ such that $m > n$.

	Let $F$ be the fraction field of $R$, and embed the $R$-module $M \cong R^n$
	into the $F$-vector space $V \cong F^n$.

	Then, because $m > n$, as elements of $V$, the elements $w_1, \dots, w_m$ are linearly dependent,
	which means there are some elements $f_1, \dots, f_m \in F$ not all zero, such that $f_1 w_1 + \cdots
	+ f_m w_m = 0$.

	By clearing denominators, we can obtain ring elements $r_1, \dots, r_m \in R$ not all zero
	such that $r_1 w_1 + \cdots + r_m w_m = 0$. This means $w_1, \dots, w_m$ cannot be a basis for $M$.
\end{proof}

Next, we prove the case where the rank $r$ is $0$.
This case needs a different strategy, but it still boils down to applying the dimension theorem for
appropriately constructed vector spaces.

\begin{theorem}
	\label{thm:uniqueness_primary_form_one_prime_torsion_module}
	Let $R$ be a PID, let $p$ be a prime element of $R$,
	and let $M \cong R/(p^{e_1}) \oplus R/(p^{e_2}) \oplus \cdots \oplus R/(p^{e_m})$
	for positive integers $e_1, \dots, e_m$.
	Then the $e_i$ are unique, up to permutations.
\end{theorem}

Intuitively, what the following proof is trying to do is:
\begin{moral}
	If we can compute the exponents $e_i$ from intrinsic properties of $M$, then the exponents must be
	unique.
\end{moral}

Let us consider a simple case --- consider $R = \ZZ$ and $M = \Zc{4}$. This module has $4$ elements, but
it's not the same as $\Zc{2} \oplus \Zc{2}$. In this case, the difference between the two modules can be
detected by the fact that in $M$, the element $1 \pmod 4$ is not zero when multiplied by $2$, on the
other hand, multiplying by $2$ makes every element in $\Zc{2} \oplus \Zc{2}$ zero.

For notational convenience,
\begin{definition}
	For $r \in R$ and a $R$-module $M$, define $r M = \{ r m \mid m \in M \}$. (Check that this is still
	a $R$-module.)
\end{definition}

Then, what the paragraph above says is that $M \not\cong \Zc{2} \oplus \Zc{2}$ because $|2 M| = 2 \neq 1
= |2 (\Zc{2} \oplus \Zc{2})|$.
In other words, in this case, counting the number of elements of $2M$ suffices to distinguish the two
modules.

For modules of the form
$M \cong R/(p^{e_1}) \oplus R/(p^{e_2}) \oplus \cdots \oplus R/(p^{e_m})$ where $R = \ZZ$,
this almost works in general --- except we also need to consider the number of elements in
$p M$, $p^2 M$, $p^3 M$, etc.

Equivalently, we may also consider the number of elements in the successive quotients:
$M/pM$, $pM/p^2 M$, $p^2 M/p^3 M$, etc.
\begin{example}
	Let $R = \ZZ$, $p = 3$, and $M = \Zc{3^2} \oplus \Zc{3^5}$. Then:
	\begin{itemize}
		\ii $|M/3M| = 9$,
		\ii $|3M/3^2 M| = 9$,
		\ii $|3^2 M/3^3 M| = 3$,
		\ii $|3^3 M/3^4 M| = 3$,
		\ii $|3^4 M/3^5 M| = 3$,
		\ii $|3^e M/3^{e+1} M| = 1$ for all integer $e \geq 5$.
	\end{itemize}
	You can already see where this is going --- each decrement of the size of the quotient
	corresponds to a prime power $p^{e_i}$.
\end{example}

When the quotient is infinite however, we can no longer do this. However, note that:
\begin{lemma}
	For each integer $e \geq 0$, then $p^e M/p^{e+1} M$ is a $R/(p)$-vector space.
\end{lemma}
Thus, instead of counting the number of elements in $p^e M/p^{e+1} M$, we count the \emph{dimension} of
the $p^e M/p^{e+1} M$ as a $R/(p)$-vector space --- by \Cref{thm:dimension_theorem}, this is indeed
intrinsic to the module $M$.

\begin{proof}[Proof of \Cref{thm:uniqueness_primary_form_one_prime_torsion_module}]
	Note that, since $M \cong R/(p^{e_1}) \oplus R/(p^{e_2}) \oplus \cdots \oplus R/(p^{e_m})$, we have
	\[ \pi(M) \cong \pi(R/(p^{e_1})) \oplus \pi(R/(p^{e_2})) \oplus \cdots \oplus \pi(R/(p^{e_m})) \]
	where $\pi(M) = p^e M/p^{e+1} M$ for any integer $e \geq 0$.

	This means, as $R/(p)$-vector space,
	\[ \dim \pi(M) = \dim \pi(R/(p^{e_1})) + \dim \pi(R/(p^{e_2})) + \cdots + \dim \pi(R/(p^{e_m})). \]

	Note that, for each term $R/(p^{e_1})$, then
	\[ \dim p^e (R/(p^{e_i})) / p^{e+1} (R/(p^{e_1})) = \begin{cases}
		1 & e < e_i \\
		0 & \text{otherwise}.
	\end{cases} \]
	With some arithmetic, you can see that the values $e_i$ are indeed uniquely determined by $\dim p^e
	M/p^{e+1} M$, up to permutation.
\end{proof}

Note that this can be easily generalized to the case where the primes in the denominator may be different
-- because for different primes $p$ and $q$ of $R$, then $p^e (R/(q))/p^{e+1} (R/(q))$ is a
$0$-dimensional $R/(p)$-vector space.

Finally, we handle the general case.
\begin{theorem}
	If $M \cong R^{\oplus r} \oplus R/(q_1) \oplus R/(q_2) \oplus \cdots \oplus R/(q_m)$,
	then the integer $r$ and the prime powers $q_i$ are unique, up to permutations.
\end{theorem}
\begin{proof}
	From the two theorems above, it suffices if we can prove that the $R^{\oplus r}$ part and the
	$R/(q_1) \oplus R/(q_2) \oplus \cdots \oplus R/(q_m)$ part are uniquely determined from $M$.

	For notational convenience, we call an element $a \in M$ a \vocab{torsion element} if there is $r \in
	R$, $r \neq 0$ such that $r a = 0$.

	Then,
	\begin{itemize}
		\ii If an element $a \in M$ has the $R^{\oplus r}$ component zero, then $q_1 q_2 \cdots q_m \cdot
		a = 0$, thus $a$ is a torsion element.
		\ii If an element $a \in M$ has the $R^{\oplus r}$ component nonzero, then $a$ is not a torsion
		element.
	\end{itemize}

	In other words, the submodule consisting of all torsion elements is identical to the submodule of the
	elements with $R^{\oplus r}$ component zero, thus is isomorphic to
	$R/(q_1) \oplus R/(q_2) \oplus \cdots \oplus R/(q_m)$.

	For notation convenience, let $\Tor(M)$ be the submodule of $M$ consisting of all torsion elements.
	Then $\Tor(M) \cong R/(q_1) \oplus R/(q_2) \oplus \cdots \oplus R/(q_m)$ and $M/\Tor(M) \cong
	R^{\oplus r}$, in other words, the $R^{\oplus r}$ part and the
	$R/(q_1) \oplus R/(q_2) \oplus \cdots \oplus R/(q_m)$ part are uniquely determined from $M$, so we're
	done.
\end{proof}


\section{Smith normal form}
The idea is now that we have reduced our problem to studying
linear maps $T \colon R^{\oplus m} \to R^{\oplus n}$,
which can be thought of as a generic matrix
\[ T = \begin{bmatrix}
		a_{11} & \dots & a_{1m} \\
		\vdots & \ddots & \vdots \\
		a_{n1} & \dots & a_{nm}
	\end{bmatrix} \]
for a basis $e_1$, \dots, $e_m$ of $R^{\oplus m}$
and $f_1$, \dots, $f_n$ of $R^{\oplus n}$.

Of course, as you might expect it ought to be possible to change the
given basis of $T$ such that $T$ has a nicer matrix form.
We already saw this in \emph{Jordan form},
where we had a map $T \colon V \to V$ and changed the basis
so that $T$ was ``almost diagonal''.
This time, we have \emph{two} sets of bases we can change,
so we would hope to get a diagonal basis, or even better.

Before proceeding let's think about how we might edit the matrix:
what operations are permitted?  Here are some examples:
\begin{itemize}
	\ii Swapping rows and columns, which just corresponds
	to re-ordering the basis.
	\ii Adding a multiple of a column to another column.
	For example, if we add $3$ times the first column to the second column,
	this is equivalent to replacing the basis
	\[ (e_1, e_2, e_3, \dots, e_m) \mapsto (e_1, e_2+3e_1, e_3, \dots, e_m). \]
	\ii Adding a multiple of a row to another row.
	One can see that adding $3$ times the first row to the second row
	is equivalent to replacing the basis
	\[ (f_1, f_2, f_3, \dots, f_n) \mapsto (f_1-3f_2, f_2, f_3, \dots, f_n). \]
\end{itemize}
More generally,
\begin{moral}
	If $A$ is an invertible $n \times n$ matrix we can
	replace $T$ with $AT$.
\end{moral}
This corresponds to replacing
\[ (f_1, \dots, f_n) \mapsto ((F A\inv)_1, \dots, (F A\inv)_n) \]
(the ``invertible'' condition just guarantees the latter is a basis).
Here, $F$ is the $n \times n$ matrix with columns being $f_1, \dots, f_n$, and $(F A\inv)_1$ denotes the
first column of $F A\inv$.

Of course similarly we can replace $T$ with $TB$
where $B$ is an invertible $m \times m$ matrix;
this corresponds to
\[ (e_1, \dots, e_m) \mapsto ((E B)_1, \dots, (E B)_m) \]
where $E$ is the $m \times m$ matrix with columns being $e_1, \dots, e_m$.

Armed with this knowledge, we can now approach:
\begin{theorem}
	[Smith normal form]
	Let $R$ be a PID.
	Let $M = R^{\oplus m}$ and $N = R^{\oplus n}$ be free $R$-modules
	and let $T \colon M \to N$ be a linear map.
	Set $k = \min\{m,n\}$.

	Then we can select a pair of new bases for $M$ and $N$ such that
	$T$ has only diagonal entries $s_1$, $s_2$, \dots, $s_k$
	and $s_1 \mid s_2 \mid \dots \mid s_k$.
\end{theorem}
So if $m > n$, the matrix should take the form
\[
	\begin{bmatrix}
		s_1 & 0 & 0 & 0 & \dots & 0 \\
		0 & s_2 & 0 & 0 & \dots & 0 \\
		\vdots & \vdots & \ddots & \vdots & \dots & \vdots \\
		0 & 0 & 0 & s_n & \dots & 0
	\end{bmatrix}.
\]
and similarly when $m \le n$.
\begin{ques}
	Show that Smith normal form implies the structure theorem.
\end{ques}

\begin{remark}
	Note that this is not a generalization of Jordan form.
	\begin{itemize}
		\ii In Jordan form we consider maps $T \colon V \to V$;
		note that the source and target space are the \emph{same},
		and we are considering one basis for the space $V$.
		\ii In Smith form the maps $T \colon M \to N$ are between
		\emph{different} modules, and we pick \emph{two} sets of bases
		(one for $M$ and one for $N$).
	\end{itemize}
\end{remark}

\begin{example}
	[Example of Smith normal form]
	To give a flavor of the idea of the proof,
	let's work through a concrete example with the $\ZZ$-matrix
	\[ \begin{bmatrix}
			18 & 38 & 48 \\
			14 & 30 & 32
		\end{bmatrix}.  \]
	The GCD of all the entries is $2$, and so motivated by this,
	we perform the \textbf{Euclidean algorithm on the left column}:
	subtract the second row from the first row,
	then three times the first row from the second:
	\[
		\begin{bmatrix}
			18 & 38 & 48 \\
			14 & 30 & 32
		\end{bmatrix}
		\mapsto
		\begin{bmatrix}
			4 & 8 & 16 \\
			14 & 30 & 32
		\end{bmatrix}
		\mapsto
		\begin{bmatrix}
			4 & 8 & 16 \\
			2 & 6 & -16
		\end{bmatrix}.
	\]
	Now that the GCD of $2$ is present, we move it to the upper-left
	by switching the two rows,
	and then kill off all the entries in the same row/column;
	since $2$ was the GCD all along, we isolate $2$ completely:
	\[
		\begin{bmatrix}
			4 & 8 & 16 \\
			2 & 6 & -16
		\end{bmatrix}
		\mapsto
		\begin{bmatrix}
			2 & 6 & -16 \\
			4 & 8 & 16
		\end{bmatrix}
		\mapsto
		\begin{bmatrix}
			2 & 6 & -16 \\
			0 & -4 & 48 \\
		\end{bmatrix}
		\mapsto
		\begin{bmatrix}
			2 & 0 & 0 \\
			0 & -4 & 48
		\end{bmatrix}.
	\]
	This reduces the problem to a $1 \times 2$ matrix.
	So we just apply the Euclidean algorithm again there:
	\[
		\begin{bmatrix}
			2 & 0 & 0 \\
			0 & -4 & 0
		\end{bmatrix}
		\mapsto
		\begin{bmatrix}
			2 & 0 & 0 \\
			0 & 4 & 0
		\end{bmatrix}.
	\]
\end{example}

Now all we have to do is generalize this proof to work
with any PID. It's intuitively clear how to do this:
the PID condition more or less lets you perform a Euclidean algorithm.

\begin{proof}
	[Proof of Smith normal form]
	Begin with a generic matrix
	\[ T = \begin{bmatrix}
		a_{11} & \dots & a_{1m} \\
		\vdots & \ddots & \vdots \\
		a_{n1} & \dots & a_{nm}
	\end{bmatrix} \]
	We want to show, by a series of operations (gradually changing the given basis)
	that we can rearrange the matrix into Smith normal form.

	Define $\gcd(x,y)$ to be any generator of the principal ideal $(x,y)$.
	\begin{claim}[``Euclidean algorithm'']
		If $a$ and $b$ are entries in the same row or column,
		we can change bases to replace $a$ with $\gcd(a,b)$
		and $b$ with something else.
	\end{claim}
	\begin{subproof}
		We do just the case of columns.
		By hypothesis, $\gcd(a,b) = xa+yb$ for some $x,y \in R$.
		We must have $(x,y) = (1)$ now (we're in a UFD).
		So there are $u$ and $v$ such that $xu + yv = 1$.
		Then
		\[
			\begin{bmatrix} x & y \\ -v & u \end{bmatrix}
			\begin{bmatrix} a \\ b  \end{bmatrix}
			= \begin{bmatrix} \gcd(a,b) \\ \text{something} \end{bmatrix}
		\]
		and the first matrix is invertible (check this!), as desired.
	\end{subproof}
	Let $s_1 = (a_{ij})_{i,j}$ be the GCD of all entries.
	Now by repeatedly applying this algorithm,
	we can cause $s$ to appear in the upper left hand corner.
	Then, we use it to kill off all the entries in the first
	row and the first column, thus arriving at a matrix
	\[ \begin{bmatrix}
		s_1 & 0 & 0 & \dots & 0 \\
		0 & a_{22}' & a_{23}' & \dots & a_{2n}' \\
		0 & a_{32}' & a_{33}' & \dots & a_{3n}' \\
		\vdots&\vdots&\vdots&\ddots&\vdots \\
		0 & a_{m2}' & a_{m3}' & \dots & a_{mn}' \\
	\end{bmatrix}. \]
	Now we repeat the same procedure with this lower-right
	$(m-1) \times (n-1)$ matrix, and so on.
	This gives the Smith normal form.
\end{proof}

With the Smith normal form, we have in the original situation that
\[ M \cong R^{\oplus d} / \img T \]
and applying the theorem to $T$ completes the proof of the structure theorem.

\section\problemhead
Now, we can apply our structure theorem!
\begin{dproblem}
	[Finite-dimensional vector spaces are all isomorphic]
	A vector space $V$ over a field $k$ has a finite spanning set of vectors.
	Show that $V \cong k^{\oplus n}$ for some $n$.
	\begin{hint}
		In the structure theorem, $k / (s_i) \in \{0,k\}$.
	\end{hint}
\end{dproblem}

\begin{dproblem}
	[Frobenius normal form]
	Let $T \colon V \to V$ where $V$ is a finite-dimensional vector space
	over an arbitrary field $k$ (not necessarily algebraically closed).
	Show that one can write $T$ as a block-diagonal matrix whose blocks
	are all of the form
	\[
		\begin{bmatrix}
			0 & 0 & 0 & \dots & 0 & \ast  \\
			1 & 0 & 0 & \dots & 0 & \ast  \\
			0 & 1 & 0 & \dots & 0 & \ast  \\
			\vdots&\vdots&\vdots&\ddots&\vdots&\vdots \\
			0 & 0 & 0 & \dots & 1 & \ast  \\
		\end{bmatrix}.
	\]
	(View $V$ as a $k[x]$-module with action $x \cdot v = T(v)$.)
	\begin{hint}
		By theorem $V \cong \bigoplus_i k[x] / (s_i)$ for some polynomials $s_i$.
		Write each block in the form described.
	\end{hint}
\end{dproblem}

\begin{dproblem}
	[Jordan normal form]
	Let $T \colon V \to V$ where $V$ is a finite-dimensional vector space
	over an arbitrary field $k$ which is algebraically closed.
	Prove that $T$ can be written in Jordan form.
	\begin{hint}
		Copy the previous proof, except using the other form of the structure theorem.
		Since $k[x]$ is algebraically closed each $p_i$ is a linear factor.
	\end{hint}
\end{dproblem}

\begin{problem}
	\onechili
	Find two abelian groups $G$ and $H$ which are not isomorphic,
	but for which there are injective homomorphisms
	$G \injto H$ and $H \injto G$.
	\begin{hint}
		The structure theorem is an anti-result here:
		it more or less implies that finitely generated abelian groups won't work.
		So, look for an infinitely generated example.
	\end{hint}
	\begin{sol}
		Take $G = \Zc3 \oplus \Zc9 \oplus \Zc9 \oplus \Zc9 \oplus \dots$
		and $H = \Zc9 \oplus \Zc9 \oplus \Zc9 \oplus \Zc9 \oplus \dots$.
		Then there are maps $G \injto H$ and $H \injto G$,
		but the groups are not isomorphic since e.g.\
		$G$ has an element $g \in G$ of order $3$
		for which there's no $g' \in G$ with $g = 3g'$.
	\end{sol}
\end{problem}

\begin{problem} % from Brian Chen
	\twochili
	Let $A \subseteq B \subseteq C$ be rings.
	Suppose $C$ is a finitely generated $A$-module.
	Does it follow that $B$ is a finitely generated $A$-module?
	% Assume $A$ is Noetherian. Show that $B$ is finitely generated as an $A$-module.
	% Find a counterexample where $A$ is not Noetherian.
	\begin{hint}
		I think the result is true if you add the assumption $A$ is Noetherian,
		so look for trouble by picking $A$ not Noetherian.
	\end{hint}
	\begin{sol}
		Nope! Pick
		\begin{align*}
			A &= \ZZ[x_1, x_2, \dots] \\
			B &= \ZZ[x_1, x_2, \dots, \eps x_1, \eps x_2, \dots] \\
			C &= \ZZ[x_1, x_2, \dots, \eps].
		\end{align*}
		where $\eps \neq 0$ but $\eps^2 = 0$.
		I think the result is true if you add the assumption $A$ is Noetherian.
	\end{sol}
\end{problem}
